---
title: "演算法和資料結構"
description: "從 JavaScript 視角學習 C 語言演算法和資料結構，理解陣列、鏈表、排序、搜尋，並對比 JavaScript 資料結構。"
---

# 演算法和資料結構

## 1. 概念介紹

### 從 JavaScript 資料結構到 C 實現

在 JavaScript 中，你有內建的陣列、物件和高階資料結構。而在 C 語言中，你必須從頭實現資料結構，這給你對記憶體佈局和效能特徵的完全控制。

> 💡 **核心概念**：C 資料結構實現提供最大的效能和記憶體效率，但需要仔細的記憶體管理和演算法設計。

## 2. 線性資料結構

<UniversalEditor title="陣列和動態陣列" compare={true}>
```javascript !! js
// JavaScript - 內建陣列
let arr = [1, 2, 3, 4, 5];

// 陣列操作
arr.push(6);           // 新增到末尾
arr.unshift(0);        // 新增到開頭
arr.pop();             // 從末尾移除
arr.shift();           // 從開頭移除
arr.splice(2, 1);      // 在索引 2 處移除

// 陣列迭代
for (let i = 0; i < arr.length; i++) {
    console.log(arr[i]);
}

// 陣列方法
arr.forEach(item => console.log(item));
arr.map(item => item * 2);
arr.filter(item => item > 3);
arr.reduce((sum, item) => sum + item, 0);

// 動態陣列行為
console.log("陣列長度:", arr.length);
arr[10] = 100; // 自動擴展
console.log("新長度:", arr.length);
```

```c !! c
#include <stdio.h>
#include <stdlib.h>

// 動態陣列結構
typedef struct {
    int* data;
    int size;
    int capacity;
} DynamicArray;

// 初始化動態陣列
DynamicArray* createArray(int initialCapacity) {
    DynamicArray* arr = (DynamicArray*)malloc(sizeof(DynamicArray));
    arr->data = (int*)malloc(initialCapacity * sizeof(int));
    arr->size = 0;
    arr->capacity = initialCapacity;
    return arr;
}

// 新增元素到末尾
void push(DynamicArray* arr, int value) {
    if (arr->size >= arr->capacity) {
        // 調整陣列大小
        arr->capacity *= 2;
        arr->data = (int*)realloc(arr->data, arr->capacity * sizeof(int));
    }
    arr->data[arr->size++] = value;
}

// 從末尾移除元素
int pop(DynamicArray* arr) {
    if (arr->size > 0) {
        return arr->data[--arr->size];
    }
    return -1; // 錯誤值
}

// 取得索引處的元素
int get(DynamicArray* arr, int index) {
    if (index >= 0 && index < arr->size) {
        return arr->data[index];
    }
    return -1; // 錯誤值
}

// 釋放陣列記憶體
void freeArray(DynamicArray* arr) {
    free(arr->data);
    free(arr);
}

int main() {
    DynamicArray* arr = createArray(5);
    
    // 新增元素
    push(arr, 1);
    push(arr, 2);
    push(arr, 3);
    push(arr, 4);
    push(arr, 5);
    
    // 列印陣列
    printf("陣列: ");
    for (int i = 0; i < arr->size; i++) {
        printf("%d ", arr->data[i]);
    }
    printf("\n");
    
    // 移除元素
    int removed = pop(arr);
    printf("移除的元素: %d\n", removed);
    
    // 列印更新後的陣列
    printf("更新後的陣列: ");
    for (int i = 0; i < arr->size; i++) {
        printf("%d ", arr->data[i]);
    }
    printf("\n");
    
    freeArray(arr);
    return 0;
}
```
</UniversalEditor>

## 3. 鏈表

<UniversalEditor title="鏈表" compare={true}>
```javascript !! js
// JavaScript - 鏈表實現
class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    }
    
    // 新增到末尾
    append(data) {
        const newNode = new Node(data);
        
        if (!this.head) {
            this.head = newNode;
        } else {
            let current = this.head;
            while (current.next) {
                current = current.next;
            }
            current.next = newNode;
        }
        this.size++;
    }
    
    // 新增到開頭
    prepend(data) {
        const newNode = new Node(data);
        newNode.next = this.head;
        this.head = newNode;
        this.size++;
    }
    
    // 移除元素
    remove(data) {
        if (!this.head) return;
        
        if (this.head.data === data) {
            this.head = this.head.next;
            this.size--;
            return;
        }
        
        let current = this.head;
        while (current.next && current.next.data !== data) {
            current = current.next;
        }
        
        if (current.next) {
            current.next = current.next.next;
            this.size--;
        }
    }
    
    // 列印鏈表
    print() {
        let current = this.head;
        while (current) {
            console.log(current.data);
            current = current.next;
        }
    }
}

// 使用範例
const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
list.prepend(0);
list.print();
```

```c !! c
#include <stdio.h>
#include <stdlib.h>

// 節點結構
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 鏈表結構
typedef struct {
    Node* head;
    int size;
} LinkedList;

// 建立新節點
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 初始化鏈表
LinkedList* createLinkedList() {
    LinkedList* list = (LinkedList*)malloc(sizeof(LinkedList));
    list->head = NULL;
    list->size = 0;
    return list;
}

// 新增到末尾
void append(LinkedList* list, int data) {
    Node* newNode = createNode(data);
    
    if (list->head == NULL) {
        list->head = newNode;
    } else {
        Node* current = list->head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
    }
    list->size++;
}

// 新增到開頭
void prepend(LinkedList* list, int data) {
    Node* newNode = createNode(data);
    newNode->next = list->head;
    list->head = newNode;
    list->size++;
}

// 移除元素
void removeElement(LinkedList* list, int data) {
    if (list->head == NULL) return;
    
    if (list->head->data == data) {
        Node* temp = list->head;
        list->head = list->head->next;
        free(temp);
        list->size--;
        return;
    }
    
    Node* current = list->head;
    while (current->next != NULL && current->next->data != data) {
        current = current->next;
    }
    
    if (current->next != NULL) {
        Node* temp = current->next;
        current->next = current->next->next;
        free(temp);
        list->size--;
    }
}

// 列印鏈表
void printList(LinkedList* list) {
    Node* current = list->head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// 釋放鏈表記憶體
void freeList(LinkedList* list) {
    Node* current = list->head;
    while (current != NULL) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }
    free(list);
}

int main() {
    LinkedList* list = createLinkedList();
    
    append(list, 1);
    append(list, 2);
    append(list, 3);
    prepend(list, 0);
    
    printf("原始鏈表: ");
    printList(list);
    
    removeElement(list, 2);
    printf("移除 2 後: ");
    printList(list);
    
    freeList(list);
    return 0;
}
```
</UniversalEditor>

## 4. 排序演算法

<UniversalEditor title="排序演算法" compare={true}>
```javascript !! js
// JavaScript - 內建排序
let arr = [64, 34, 25, 12, 22, 11, 90];
arr.sort((a, b) => a - b);
console.log("排序後:", arr);

// 氣泡排序實現
function bubbleSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交換
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}

// 快速排序實現
function quickSort(arr) {
    if (arr.length <= 1) return arr;
    
    const pivot = arr[Math.floor(arr.length / 2)];
    const left = arr.filter(x => x < pivot);
    const middle = arr.filter(x => x === pivot);
    const right = arr.filter(x => x > pivot);
    
    return [...quickSort(left), ...middle, ...quickSort(right)];
}

// 測試排序
let testArr = [64, 34, 25, 12, 22, 11, 90];
console.log("原始陣列:", testArr);
console.log("氣泡排序:", bubbleSort([...testArr]));
console.log("快速排序:", quickSort([...testArr]));
```

```c !! c
#include <stdio.h>
#include <stdlib.h>

// 交換函數
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 氣泡排序
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }
}

// 快速排序分割
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

// 快速排序
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 列印陣列
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始陣列: ");
    printArray(arr, n);
    
    // 氣泡排序
    int bubbleArr[7];
    for (int i = 0; i < n; i++) {
        bubbleArr[i] = arr[i];
    }
    bubbleSort(bubbleArr, n);
    printf("氣泡排序: ");
    printArray(bubbleArr, n);
    
    // 快速排序
    int quickArr[7];
    for (int i = 0; i < n; i++) {
        quickArr[i] = arr[i];
    }
    quickSort(quickArr, 0, n - 1);
    printf("快速排序: ");
    printArray(quickArr, n);
    
    return 0;
}
```
</UniversalEditor>

## 5. 搜尋演算法

<UniversalEditor title="搜尋演算法" compare={true}>
```javascript !! js
// JavaScript - 內建搜尋方法
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

// 線性搜尋
function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;
        }
    }
    return -1;
}

// 二分搜尋（需要排序陣列）
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

// 測試搜尋演算法
console.log("陣列:", arr);
console.log("線性搜尋 7:", linearSearch(arr, 7));
console.log("二分搜尋 7:", binarySearch(arr, 7));
console.log("線性搜尋 11:", linearSearch(arr, 11));
console.log("二分搜尋 11:", binarySearch(arr, 11));
```

```c !! c
#include <stdio.h>

// 線性搜尋
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

// 二分搜尋（需要排序陣列）
int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

// 列印搜尋結果
void printSearchResult(int result, int target) {
    if (result != -1) {
        printf("找到 %d 在索引 %d\n", target, result);
    } else {
        printf("%d 在陣列中未找到\n", target);
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("陣列: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    // 測試線性搜尋
    int target1 = 7;
    int result1 = linearSearch(arr, n, target1);
    printf("線性搜尋: ");
    printSearchResult(result1, target1);
    
    // 測試二分搜尋
    int target2 = 7;
    int result2 = binarySearch(arr, 0, n - 1, target2);
    printf("二分搜尋: ");
    printSearchResult(result2, target2);
    
    // 測試未找到
    int target3 = 11;
    int result3 = linearSearch(arr, n, target3);
    printf("線性搜尋: ");
    printSearchResult(result3, target3);
    
    return 0;
}
```
</UniversalEditor>

## 6. 常見陷阱
- **記憶體洩漏**：始終釋放資料結構中分配的記憶體
- **緩衝區溢位**：在存取元素前檢查陣列邊界
- **空指標解參考**：始終檢查空指標
- **演算法複雜度**：注意時間和空間複雜度
- **資料結構選擇**：為問題選擇適當的結構

## 7. 練習題
1. 使用陣列或鏈表實現堆疊資料結構。
2. 撰寫函數以迭代和遞迴方式反轉鏈表。
3. 實現合併排序並與快速排序比較效能。
4. 建立帶衝突解決的雜湊表實現。

## 8. 效能分析
- **陣列**：O(1) 存取，O(n) 插入/刪除
- **鏈表**：O(n) 存取，O(1) 在兩端插入/刪除
- **氣泡排序**：O(n²) 時間複雜度
- **快速排序**：O(n log n) 平均，O(n²) 最壞情況
- **線性搜尋**：O(n) 時間複雜度
- **二分搜尋**：O(log n) 時間複雜度

---

> **小結**：C 演算法和資料結構的實現提供最大的控制和效能。理解記憶體管理、演算法複雜度和選擇適當的資料結構對高效的 C 程式設計至關重要。 